class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //这道题目其实就是在原数组中找到值，这个值就是整个数组和的一半
        int n = nums.size();
        int target = 0;
        for(auto e:nums)
        {
            target+=e;
        }
        if(target%2!=0)
        {
            return false;//奇数不可能是正确的
        }
        target /=2;
        //下面就可以将这个题目转化为01背包问题了
        //dp[i][j]代表从前i个元素中进行选择，总和等于j是否能够分割完成
        //对于第i个元素，我可以选择1个也可以不选择
        //如果我不选择第i个元素
        //dp[i][j] = dp[i-1][j]
        //我选择了第i个元素dp[i][j] = dp[i-1][j-nums[i]]
        vector<vector<int>> dp(n+1,vector<int>(target+1,false));
        dp[0][0] = true;
        for(int i = 1;i<=n;i++)
        {
            for(int j = 1;j<=target;j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1])
                {
                    dp[i][j] = dp[i-1][j-nums[i-1]]?dp[i-1][j-nums[i-1]]:dp[i][j];
                }
            }
        }
        return dp[n][target];        
    }
};//不使用记忆化数组
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 这道题目其实就是在原数组中找到值，这个值就是整个数组和的一半
        int n = nums.size();
        int target = 0;
        for(auto e:nums)
        {
            target+=e;
        }
        if(target%2!=0)
        {
            return false;//奇数不可能是正确的
        }
        target /=2;
        //下面就可以将这个题目转化为01背包问题了
        //dp[i][j]代表从前i个元素中进行选择，总和等于j是否能够分割完成
        //对于第i个元素，我可以选择1个也可以不选择
        //如果我不选择第i个元素
        //dp[i][j] = dp[i-1][j]
        //我选择了第i个元素dp[i][j] = dp[i-1][j-nums[i]]
        vector<int> dp(target+1,false);
        dp[0] = true;
        for(int i = 1;i<=n;i++)
        {
            for(int j = target;j>=nums[i-1];j--)
            {
                dp[j] = dp[j-nums[i-1]]?dp[j-nums[i-1]]:dp[j];
            }
        }
        return dp[target];        
    }
};//使用记忆化数组